package Algorithm.Array;

/**
 * @Author ykeezy
 * @Date：2024/5/1112:44
 * @PacakageName：
 * @ClassName：2024/5/11
 * @Description：二分查找法
 * @Version 1.0
 */
class BinarySearch {

    //二分查找法
    //给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
    // 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
    public static  int BinarySearch(int[] array,int desData){

        int left  = 0;
        int right = array.length-1;
        int mid = 0;
        while ( right>=left ){
            mid = (right+left)/2;
            if ( array[mid] == desData){
                return mid;
            } else if (array[mid] < desData) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return -1;
    }

    //搜索插入位置
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    //
    //你可以假设数组中无重复元素。
    public static int SearchTargetIndex(int[] array,int target){
        int left  = 0;
        int right = array.length-1;
        int mid = 0;
        while ( right>=left ){
            mid = (right+left)/2;
            if ( array[mid] == target){
                return mid;
            } else if (array[mid] < target) {
                left = mid+1;
            }else {
                right = mid-1;

            }

        }
        //执行到此处必有 right<left
        if (right<0){
            //对right == -1的情况做判断，避免数组越界
            return 0;
            //此时的mid为最后一次循环中的mid,最后一次循环时 mid == left ==right，
            // 当arrayp[mid]小于target就说明target应该被插入在数组的最右边
        } else if (array[mid] < target){
            return left;
            //此为判断target是否应该插入到倒数第二次循环的left和right的中间，left == mid说明target小于倒数第二次循环中的right，
            // 而array[right]<target又说明target大于倒数第二次循环中的left，故target应该插在倒数第二次循环时的left和right的中间。
        } else if (mid == left & array[right]<target) {
            return left;
        }   //插入到左边

        else return 0;

    }




    public static void main(String[] args) {

        int[] array = {1,1,1,1,1};
        System.out.println(BinarySearch(array,3));
        System.out.println(SearchTargetIndex(array,2));

    }

}

class SearchRangeAlgorithmLeetcodeVersion{

    //在排序数组中查找元素的第一个和最后一个位置
    //给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    //
    //如果数组中不存在目标值 target，返回 [-1, -1]。
    //
    //进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？
    //使用条件控制的递归来控制二分法的调用——太难了
    public static int[] SearchRange(int[] array , int target){

        if (array.length==0){
            return new int[]{-1,-1};
        }
        int FirstTargetIndex = FindFirstTargetIndex(array, target);
        if (FirstTargetIndex==-1){
            return new int[]{-1,-1};
        }
        int LastTargetIndex = FindLastTargetIndex(array, target);
        return new int[]{FirstTargetIndex,LastTargetIndex};

    }

    private static int FindLastTargetIndex(int[] array, int target) {

        int right = array.length-1;
        int left = 0;
        int mid = 0;
        //一步步调试这个while循环，观察left，mid，right的值就能理解这个算法了
        while (left<right){
            mid = left + ((right-left)/2) +1;
            if (array[mid]==target){
                left = mid;
            } else if (array[mid]<target) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        if (array[left]==target){
            return left;
        }
        return -1;

    }

    private static int FindFirstTargetIndex(int[] array, int target) {

        int right = array.length-1;
        int left = 0;
        int mid = 0;
        while (left<right){
            mid = left + ((right-left)/2);
            if (array[mid]==target){
                right = mid;
            } else if (array[mid]<target) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        if (array[right]==target){
            return right;
        }
        return -1;

    }

    public static void main(String[] args) {

        int[] array = {1,1,1,1,1};
        int target = 1;
        for (int i :SearchRange(array, target)
             ) {
            System.out.println(i);
        }

    }

}
/*    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

        如果数组中不存在目标值 target，返回 [-1, -1]。

        进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？*/
class SearchRangeMyVersion{

    public static int[] searchRange(int[] array, int target){

        //若为空数组，return new int[]{-1,-1};
        if (array.length == 0){
            return new int[]{-1,-1};
        }
        int left = 0;
        int right = array.length-1;
        //若找不到第一个Target的下标，则return new int[]{-1,-1};
        int FirstTargetIndex = FindFirstTargetIndex(array,target);
        if (FirstTargetIndex == -2){
            return new int[]{-1,-1};
        }
        int LastTargetIndex = FindLastTargetIndex(array, target);
        //若最后一个Target的下标找不到，则return new int[]{-1,-1};
        if (LastTargetIndex==-2){
            return new int[]{-1,-1};
        }
        //只要第一个Target和最后一个Target的下标任意一个>=0，则return new int[]{FirstTargetIndex, LastTargetIndex};
        if (FirstTargetIndex>=0 || LastTargetIndex>=0){
            return new int[]{FirstTargetIndex, LastTargetIndex};
        }
        return new int[]{-1,-1};

    }

    private static int FindLastTargetIndex(int[] array, int target) {

        int LastTargetIndex = -2;
        int left = 0;
        int right = array.length-1;
        int mid = 0;
        while (left <= right){
            mid = left + ((right - left)/2);
            if (array[mid] == target){
                //找到了target则用LastTargetIndex先存储
                LastTargetIndex = mid;
                left = mid + 1;
            } else if (array[mid] > target){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return LastTargetIndex;

    }

    private static int FindFirstTargetIndex(int[] array, int target) {

        int FirstTargetIndex = -2;
        int left = 0;
        int right = array.length-1;
        int mid = 0;
        while (left <= right){
            mid = left + ((right - left)/2);
            if (array[mid] == target){
                //找到了target则用FirstTargetIndex先存储
                FirstTargetIndex = mid;
                right = mid - 1;
            } else if ( array[mid] < target ){
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        return FirstTargetIndex;

    }

    public static void main(String[] args) {

        for (int i:searchRange(new int[]{5,7,7,8,8,10},6)
             ) {
            System.out.println(i);
        }

    }

}

/*    给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

        由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

        注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。*/
class ReturnXofSquareArithmeticSquareRoot{

    public static int findXofSquareArithmeticRoot(int x){

        if (x < 0){
            return -1;
        }
        if (x == 0){
            return 0;
        }
        int right = x;
        int left = 0;
        //注意后面两个ArithmeticSquareRoot相乘时可能会因为超过int类型最大值而获得一个错误的值，故在这里应该将Arithmetic声明为long类型
        long ArithmeticSqaureRoot = -1;
        while (left <= right){
            //left + (right - left)/2结果上等价于 (left + right)/2，但前者可避免两个数相加造成的溢出
            ArithmeticSqaureRoot = left + (right - left)/2;
            long rootProduct = (ArithmeticSqaureRoot * ArithmeticSqaureRoot); //需要多次用到这个平方，故写成一个新的变量增加易读性，注意int越界问题，将其声明为long类型
            /*注意这里判断区间的或是否找到 ArithmeticSqaureRoot 条件是rootProduct与 x 之间的关系
            若rootProduct == x  || rootProduct < x < ArithmeticProduct,
            则return rootProduct;*/
            if (rootProduct == x || (x < ((ArithmeticSqaureRoot +1) * (ArithmeticSqaureRoot +1)) &&
                    rootProduct < x) ){
                return (int) ArithmeticSqaureRoot;
            }else if ( rootProduct > x ){
                right = (int) ArithmeticSqaureRoot - 1;
            }else {
                left = (int) ArithmeticSqaureRoot + 1;
            }
        }
        return -1;

    }

    public static void main(String[] args) {

        System.out.println( findXofSquareArithmeticRoot(2147395599) );

    }

}

//      有效的完全平方数
/*    给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

        完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

        不能使用任何内置的库函数，如  sqrt 。*/
class UsefulCompleteSquareNums{

    public static boolean IsCompleteSquareNum ( int num ){

        if (num < 1){
            return false;
        }
        if (num == 1){
            return true;
        }
        int outcome = FindCompleteSqaureNum(num);
        return outcome > 0 ? true : false;

    }

    private static int FindCompleteSqaureNum ( int num ) {

        int left = 1;
        int right = num;
        long SquareRoot = -1;
        while (left <= right){
            SquareRoot = left + ( right - left ) / 2;
            long rootProduct = SquareRoot * SquareRoot;
            if ( rootProduct == num ) {
                return (int) rootProduct;
            } else if ( rootProduct < num ) {
                left = (int) SquareRoot + 1;
            }else {
                right = (int) SquareRoot -1;
            }
        }
        return -1;

    }

    public static void main(String[] args) {

        System.out.println( IsCompleteSquareNum( 4 ) );

    }

}
